home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / python2.4 / test / test_heapq.pyc (.txt) < prev    next >
Encoding:
Python Compiled Bytecode  |  2005-10-18  |  12.0 KB  |  370 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyc (Python 2.4)
  3.  
  4. '''Unittests for heapq.'''
  5. from heapq import heappush, heappop, heapify, heapreplace, nlargest, nsmallest
  6. import random
  7. import unittest
  8. from test import test_support
  9. import sys
  10.  
  11. def heapiter(heap):
  12.     
  13.     try:
  14.         while None:
  15.             yield heappop(heap)
  16.     except IndexError:
  17.         pass
  18.  
  19.  
  20.  
  21. class TestHeap(unittest.TestCase):
  22.     
  23.     def test_push_pop(self):
  24.         heap = []
  25.         data = []
  26.         self.check_invariant(heap)
  27.         for i in range(256):
  28.             item = random.random()
  29.             data.append(item)
  30.             heappush(heap, item)
  31.             self.check_invariant(heap)
  32.         
  33.         results = []
  34.         while heap:
  35.             item = heappop(heap)
  36.             self.check_invariant(heap)
  37.             results.append(item)
  38.         data_sorted = data[:]
  39.         data_sorted.sort()
  40.         self.assertEqual(data_sorted, results)
  41.         self.check_invariant(results)
  42.         self.assertRaises(TypeError, heappush, [])
  43.         
  44.         try:
  45.             self.assertRaises(TypeError, heappush, None, None)
  46.             self.assertRaises(TypeError, heappop, None)
  47.         except AttributeError:
  48.             pass
  49.  
  50.  
  51.     
  52.     def check_invariant(self, heap):
  53.         for pos, item in enumerate(heap):
  54.             if pos:
  55.                 parentpos = pos - 1 >> 1
  56.                 self.assert_(heap[parentpos] <= item)
  57.                 continue
  58.         
  59.  
  60.     
  61.     def test_heapify(self):
  62.         for size in range(30):
  63.             heap = [ random.random() for dummy in range(size) ]
  64.             heapify(heap)
  65.             self.check_invariant(heap)
  66.         
  67.         self.assertRaises(TypeError, heapify, None)
  68.  
  69.     
  70.     def test_naive_nbest(self):
  71.         data = [ random.randrange(2000) for i in range(1000) ]
  72.         heap = []
  73.         for item in data:
  74.             heappush(heap, item)
  75.             if len(heap) > 10:
  76.                 heappop(heap)
  77.                 continue
  78.             []
  79.         
  80.         heap.sort()
  81.         self.assertEqual(heap, sorted(data)[-10:])
  82.  
  83.     
  84.     def test_nbest(self):
  85.         data = [ random.randrange(2000) for i in range(1000) ]
  86.         heap = data[:10]
  87.         heapify(heap)
  88.         for item in data[10:]:
  89.             if item > heap[0]:
  90.                 heapreplace(heap, item)
  91.                 continue
  92.             []
  93.         
  94.         self.assertEqual(list(heapiter(heap)), sorted(data)[-10:])
  95.         self.assertRaises(TypeError, heapreplace, None)
  96.         self.assertRaises(TypeError, heapreplace, None, None)
  97.         self.assertRaises(IndexError, heapreplace, [], None)
  98.  
  99.     
  100.     def test_heapsort(self):
  101.         for trial in xrange(100):
  102.             size = random.randrange(50)
  103.             data = [ random.randrange(25) for i in range(size) ]
  104.             heap_sorted = [ heappop(heap) for i in range(size) ]
  105.             self.assertEqual(heap_sorted, sorted(data))
  106.         
  107.  
  108.     
  109.     def test_nsmallest(self):
  110.         data = [ random.randrange(2000) for i in range(1000) ]
  111.         for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100):
  112.             self.assertEqual(nsmallest(n, data), sorted(data)[:n])
  113.         
  114.  
  115.     
  116.     def test_largest(self):
  117.         data = [ random.randrange(2000) for i in range(1000) ]
  118.         for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100):
  119.             self.assertEqual(nlargest(n, data), sorted(data, reverse = True)[:n])
  120.         
  121.  
  122.  
  123.  
  124. class LenOnly:
  125.     '''Dummy sequence class defining __len__ but not __getitem__.'''
  126.     
  127.     def __len__(self):
  128.         return 10
  129.  
  130.  
  131.  
  132. class GetOnly:
  133.     '''Dummy sequence class defining __getitem__ but not __len__.'''
  134.     
  135.     def __getitem__(self, ndx):
  136.         return 10
  137.  
  138.  
  139.  
  140. class CmpErr:
  141.     '''Dummy element that always raises an error during comparison'''
  142.     
  143.     def __cmp__(self, other):
  144.         raise ZeroDivisionError
  145.  
  146.  
  147.  
  148. def R(seqn):
  149.     '''Regular generator'''
  150.     for i in seqn:
  151.         yield i
  152.     
  153.  
  154.  
  155. class G:
  156.     '''Sequence using __getitem__'''
  157.     
  158.     def __init__(self, seqn):
  159.         self.seqn = seqn
  160.  
  161.     
  162.     def __getitem__(self, i):
  163.         return self.seqn[i]
  164.  
  165.  
  166.  
  167. class I:
  168.     '''Sequence using iterator protocol'''
  169.     
  170.     def __init__(self, seqn):
  171.         self.seqn = seqn
  172.         self.i = 0
  173.  
  174.     
  175.     def __iter__(self):
  176.         return self
  177.  
  178.     
  179.     def next(self):
  180.         if self.i >= len(self.seqn):
  181.             raise StopIteration
  182.         
  183.         v = self.seqn[self.i]
  184.         self.i += 1
  185.         return v
  186.  
  187.  
  188.  
  189. class Ig:
  190.     '''Sequence using iterator protocol defined with a generator'''
  191.     
  192.     def __init__(self, seqn):
  193.         self.seqn = seqn
  194.         self.i = 0
  195.  
  196.     
  197.     def __iter__(self):
  198.         for val in self.seqn:
  199.             yield val
  200.         
  201.  
  202.  
  203.  
  204. class X:
  205.     '''Missing __getitem__ and __iter__'''
  206.     
  207.     def __init__(self, seqn):
  208.         self.seqn = seqn
  209.         self.i = 0
  210.  
  211.     
  212.     def next(self):
  213.         if self.i >= len(self.seqn):
  214.             raise StopIteration
  215.         
  216.         v = self.seqn[self.i]
  217.         self.i += 1
  218.         return v
  219.  
  220.  
  221.  
  222. class N:
  223.     '''Iterator missing next()'''
  224.     
  225.     def __init__(self, seqn):
  226.         self.seqn = seqn
  227.         self.i = 0
  228.  
  229.     
  230.     def __iter__(self):
  231.         return self
  232.  
  233.  
  234.  
  235. class E:
  236.     '''Test propagation of exceptions'''
  237.     
  238.     def __init__(self, seqn):
  239.         self.seqn = seqn
  240.         self.i = 0
  241.  
  242.     
  243.     def __iter__(self):
  244.         return self
  245.  
  246.     
  247.     def next(self):
  248.         3 // 0
  249.  
  250.  
  251.  
  252. class S:
  253.     '''Test immediate stop'''
  254.     
  255.     def __init__(self, seqn):
  256.         pass
  257.  
  258.     
  259.     def __iter__(self):
  260.         return self
  261.  
  262.     
  263.     def next(self):
  264.         raise StopIteration
  265.  
  266.  
  267. from itertools import chain, imap
  268.  
  269. def L(seqn):
  270.     '''Test multiple tiers of iterators'''
  271.     return chain(imap((lambda x: x), R(Ig(G(seqn)))))
  272.  
  273.  
  274. class TestErrorHandling(unittest.TestCase):
  275.     
  276.     def test_non_sequence(self):
  277.         for f in (heapify, heappop):
  278.             self.assertRaises(TypeError, f, 10)
  279.         
  280.         for f in (heappush, heapreplace, nlargest, nsmallest):
  281.             self.assertRaises(TypeError, f, 10, 10)
  282.         
  283.  
  284.     
  285.     def test_len_only(self):
  286.         for f in (heapify, heappop):
  287.             self.assertRaises(TypeError, f, LenOnly())
  288.         
  289.         for f in (heappush, heapreplace):
  290.             self.assertRaises(TypeError, f, LenOnly(), 10)
  291.         
  292.         for f in (nlargest, nsmallest):
  293.             self.assertRaises(TypeError, f, 2, LenOnly())
  294.         
  295.  
  296.     
  297.     def test_get_only(self):
  298.         for f in (heapify, heappop):
  299.             self.assertRaises(TypeError, f, GetOnly())
  300.         
  301.         for f in (heappush, heapreplace):
  302.             self.assertRaises(TypeError, f, GetOnly(), 10)
  303.         
  304.         for f in (nlargest, nsmallest):
  305.             self.assertRaises(TypeError, f, 2, GetOnly())
  306.         
  307.  
  308.     
  309.     def test_get_only(self):
  310.         seq = [
  311.             CmpErr(),
  312.             CmpErr(),
  313.             CmpErr()]
  314.         for f in (heapify, heappop):
  315.             self.assertRaises(ZeroDivisionError, f, seq)
  316.         
  317.         for f in (heappush, heapreplace):
  318.             self.assertRaises(ZeroDivisionError, f, seq, 10)
  319.         
  320.         for f in (nlargest, nsmallest):
  321.             self.assertRaises(ZeroDivisionError, f, 2, seq)
  322.         
  323.  
  324.     
  325.     def test_arg_parsing(self):
  326.         for f in (heapify, heappop, heappush, heapreplace, nlargest, nsmallest):
  327.             self.assertRaises(TypeError, f, 10)
  328.         
  329.  
  330.     
  331.     def test_iterable_args(self):
  332.         for f in (nlargest, nsmallest):
  333.             for s in ('123', '', range(1000), ('do', 1.2), xrange(2000, 2200, 5)):
  334.                 for g in (G, I, Ig, L, R):
  335.                     self.assertEqual(f(2, g(s)), f(2, s))
  336.                 
  337.                 self.assertEqual(f(2, S(s)), [])
  338.                 self.assertRaises(TypeError, f, 2, X(s))
  339.                 self.assertRaises(TypeError, f, 2, N(s))
  340.                 self.assertRaises(ZeroDivisionError, f, 2, E(s))
  341.             
  342.         
  343.  
  344.  
  345.  
  346. def test_main(verbose = None):
  347.     BuiltinFunctionType = BuiltinFunctionType
  348.     import types
  349.     test_classes = [
  350.         TestHeap]
  351.     if isinstance(heapify, BuiltinFunctionType):
  352.         test_classes.append(TestErrorHandling)
  353.     
  354.     test_support.run_unittest(*test_classes)
  355.     if verbose and hasattr(sys, 'gettotalrefcount'):
  356.         import gc
  357.         counts = [
  358.             None] * 5
  359.         for i in xrange(len(counts)):
  360.             test_support.run_unittest(*test_classes)
  361.             gc.collect()
  362.             counts[i] = sys.gettotalrefcount()
  363.         
  364.         print counts
  365.     
  366.  
  367. if __name__ == '__main__':
  368.     test_main(verbose = True)
  369.  
  370.